package com.heima.datastructure.priorityqueue;

import com.heima.datastructure.queue.Queue;

import java.util.Iterator;

/**
 * 基于无序数组实现优先级队列
 *
 * @param <E> 队列中的元素类型，必须实现Priority接口
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/2 21:14
 */
// <E extends Priority>常用于泛型类或方法的定义，这里的extends既可以是表示继承也可以表示实现，即Priority既可以是类也可以是接口
// <? extends Priority>常用于泛型方法的参数、变量声明或返回类型，特别是需要读取但不修改数据时，这里的extends既可以是表示继承也可以表示实现，即E既可以是类也可以是接口。
// java开发者偷懒没有引入新的关键字，直接将就extends用了
public class PriorityQueue1<E extends Priority> implements Queue<E>, Iterable<Integer> {
    // 思路：
    // 1、队列的元素要实现优先级接口，可以返回一个优先级以比较
    // 2、入队就在数组末尾新增
    // 3、poll就找到优先级最高的元素返回并删除，后面的元素前移
    // 4、入队固定在队尾，用一个size足矣，出队不确定，head、tail就不要了

    // arr中存的是一个个地址，引用的分别是Priority的实现类E的实例
    // 假设这里的E是Entry
    // 就相当于执行Priority p1 = new Entry();
    // 就相当于执行Priority p2 = new Entry();
    // 就相当于执行Priority p3 = new Entry();
    // ...
    // 把p1，p2，p3...存到这个数组中去，
    // 当从arr中取出p1时，只能调用Priority有的方法，又p1引用的Entry的实例，而且Entry是重写或实现了Priority中的方法的，所以会调用Priority中的方法就会被覆盖，实则调用的子类或实现类的该方法
    private Priority[] arr; // 无序数组
    private int size; // 数组的大小，默认初始化为0，同时也指向数组最后一个元素后一个元素

    /**
     * 构造方法初始化
     *
     * @param capacity 容量
     */
    public PriorityQueue1(int capacity) {
        arr = new Priority[capacity];
    }

    /**
     * 入队 O(1)
     *
     * @param value 待插入值
     * @return 入队成功返回true
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        arr[size++] = value; // 多态
        return true;
    }

    /**
     * 出队并删除 O(n)
     *
     * @return 出队的元素
     */
    @SuppressWarnings("all")
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int index = findMaxPriorityIndex();
        E value = (E) arr[index];
        remove(index);
        return value;
    }

    /**
     * 获取优先级最高的元素
     *
     * @return 优先级最高的元素
     */
    @SuppressWarnings("all")
    @Override
    public E peek() {
        return (E) arr[findMaxPriorityIndex()];
    }

    /**
     * 判断是否为空
     *
     * @return 空返回true
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 判断是否为满
     *
     * @return 为满返回true
     */
    @Override
    public boolean isFull() {
        return size == arr.length;
    }

    /**
     * 非空情况下找到优先级最高的元素的索引
     *
     * @return 索引
     */
    private int findMaxPriorityIndex() {
        int index = 0;
        for (int i = 0; i < size; i++) {
            if (arr[i].priority() > arr[index].priority()) {
                index = i;
            }
        }
        return index;
    }

    /**
     * 删除索引为index的元素
     *
     * @param index 索引
     */
    private void remove(int index) {
        if (index + 1 == size) {
            arr[index] = null;
        } else {
            System.arraycopy(arr, index + 1, arr, index, size - index - 1);
        }
        size--;
    }

    /**
     * 迭代器遍历时取出优先级
     *
     * @return 优先级迭代器
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int index = 0;

            @Override
            public boolean hasNext() {
                return index != size;
            }

            @Override
            public Integer next() {
                return arr[index++].priority();
            }
        };
    }

    /**
     * 扩容
     *
     * @param capacity 扩容
     * @throws IllegalArgumentException capacity太小
     */
    @SuppressWarnings("all")
    public void expansion(int capacity) {
        if (capacity <= arr.length) {
            throw new IllegalArgumentException("参数capacity不能比" + arr.length + "小");
        }
        Priority[] array = new Priority[capacity];
        System.arraycopy(arr, 0, array, 0, size);
        arr = array;
    }
}
